package 徒步旅行中的解题问题;
public class ans {
    public static int solution(int n, int k, int[] data) {
        int[][] dp = new int[n + 10][k + 10];

        // 初始化第0天的状态
        for (int i = 1; i <= k; i++) dp[0][i] = i * data[0];
        // 初始化超出携带上限的状态
        for (int i = 0; i < n; i++) dp[i][k + 1] = 0x3f3f3f3f;

        // 动态规划状态转移
        for (int i = 1; i < n; i++) {   //天数变化
            for (int j = 1; j <= k; j++) {  //每一天结束时可能携带的食物
                dp[i][j] = 0x3f3f3f3f;
                for (int w = 1; w <= j + 1; w++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i - 1][w] + (j - w + 1) * data[i]);
                }
            }
        }

        // 返回最终结果
        return dp[n - 1][1];
    }
    public static void main(String[] args) {
        // 测试
        System.out.println(solution(5, 2, new int[]{1, 2, 3, 3, 2}) == 9);
    }
}